package algorithm_primary.studyClass.新手课程.链表相加;

/**
 * @author mengHao.heng
 * @date 2023/6/6 13:56
 * @description TestMain
 */
public class TestMain {

    /**
     * node1     4->6->9->8->6
     * node2     6->3->5->0->7->8->9
     * 输出       0->0->5->9->3->9->9
     * <p>
     * 思路: 一共分为三步走   先把这两个节点的长度分别求出来并且确定谁是长的谁是短的
     * 第一步  先走短的链表为准  和短长的同时相加
     * 第二步  当短的循环完毕以后长的肯定还没完毕  长的接着加
     * 第三步  两个都走完了 这时候看是否还需要再进位   如果需要进位那么再加一个 1
     */
    public static void main(String[] args) {
        ListNode node1 = new ListNode(4);
        node1.next = new ListNode(6);
        node1.next.next = new ListNode(9);
        node1.next.next.next = new ListNode(8);
        node1.next.next.next.next = new ListNode(6);
        ListNode node2 = new ListNode(6);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(5);
        node2.next.next.next = new ListNode(0);
        node2.next.next.next.next = new ListNode(7);
        node2.next.next.next.next.next = new ListNode(8);
        node2.next.next.next.next.next.next = new ListNode(9);
        node1 = addNode(node1,node2);
        System.out.println(node1);
    }

    public static ListNode addNode(ListNode node1, ListNode node2) {
        int l1 = getLenth(node1);
        int l2 = getLenth(node2);
        // 寻找长的node
        ListNode l = l1 >= l2 ? node1 : node2;
        // 寻找短的node
        ListNode s = l == node1 ? node2 : node1;
        // 记住最开始头位置
        ListNode result = l;
        ListNode lEnd = l;

        //第一步  先走短的链表为准  和短长的同时相加
        int binary = 0;
        while (s != null) {
            int val = (s.val + l.val + binary);
            binary = val / 10;
            val = val % 10;
            l.val = val;
            s = s.next;
            lEnd = l;
            l = l.next;
        }
        while (l != null) {
            int val = l.val + binary;
            binary = val / 10;
            val = val % 10;
            l.val = val;
            lEnd = l;
            l = l.next;
        }
        // 说明还需要进位一个
        if (binary != 0) {
            lEnd.next = new ListNode(1);
        }
        return result;
    }

    private static int getLenth(ListNode node) {
        int count = 0;
        while (node != null) {
            count++;
            node = node.next;
        }
        return count;
    }
}
